#include "stdafx.h"
#include "FirstWord.h"

namespace compile
{
	FirstWord::FirstWord()
	{
	}

	// 通过传入的文法初始化First集合
	// parm: syntax {Syntax*} - 文法类指针
	FirstWord::FirstWord(Syntax* syntax)
	{
		vector<Word>word_vector = (*syntax).getWordVector();
		calculateFirst(word_vector);
		word_vector.clear();
	}

	FirstWord::~FirstWord()
	{
		first.clear();
	}

	// 打印First集合
	void FirstWord::printFirst() const
	{
		cout << endl << "First Set:" << endl;
		for (auto it = first.begin(); it != first.end(); ++it)
		{
			cout << it->first << '\t';
			for (auto is = it->second.begin(); is != it->second.end(); ++is)
			{
				cout << *is << ',';
			}
			cout << endl;
		}
	}

	// 计算First集合
	// parma: word_vector {vector<Word>} - 获取到的词法数组
	void FirstWord::calculateFirst(vector<Word>word_vector)
	{
		for (UNI i = 0; i < word_vector.size(); ++i)
		{
			// 获取当前词法
			Word this_word = word_vector.at(i);
			set<string>insert_set;
			string key = this_word.getKey();
			string content = this_word.getContent();


			// checkEnd函数要改，不能直接迭代First，要迭代word_vector
			// 判断首字符是否为终结符
			if (ifEndSign(content[0]))
			{
				char temp[2];
				temp[0] = content[0];
				temp[1] = '\0';
				insert_set.insert(temp);
				insertSet(key, &insert_set);
				continue;
			}
			else
			{

				// 连续非终结符个数
				UNI j;
				set<string>read_set;

				// 还需要判断该非终结符是否能导出空串，导不出就跳出循环
				for (j = 0; !ifEndSign(content[j])
					&& j < content.length(); ++j)
				{


					calculateFirst(&insert_set,
						content[j],
						&word_vector);

					
					read_set.insert(polyfillChar(content[j]));
				}
				
				// 迭代了所有标识符
				if (j >= content.length())
				{
					UNI flag = 0;

					for (auto k = read_set.begin(); 
						k != read_set.end(); 
						++k)
					{
						set<string>checked_set;
						if (checkEnd(*k, &checked_set))
						{
							flag++;
						}
						checked_set.clear();
					}

					if (flag == read_set.size())
					{
						insert_set.insert("$");
					}
				}
				
			}

			insertSet(key, &insert_set);
		}
	}

	// 判断是否是终结符
	// Param: sign {char} - 传入的判断字符
	// Retrun: true - 是终结符
	//			false - 不是终结符
	bool FirstWord::ifEndSign(char sign)
	{
		if (!(sign >= 'A' && sign <= 'Z'))
		{
			return true;
		}
		return false;
	}


	// 计算当首字符不为终结符时的First集合
	// Param: insert_set {set<string>*} - 需要插入first里的set指针
	//		count_key {char} - 传入的非终结符标记
	//		word_vector {vector<Word>*} - 文法数组指针
	void FirstWord::calculateFirst(set<string> *insert_set,
		char count_key,
		vector<Word>*word_vector) const
	{
		// 进行char和string的兼容
		string a = polyfillChar(count_key);

		vector<string>syntax;

		// 查找当前key对应的句法
		for (auto it = (*word_vector).begin();
			it != (*word_vector).end();
			++it)
		{
			if ((*it).getKey() == a)
			{
				syntax.push_back((*it).getContent());
			}
		}

		// 循环每个句法，输入First
		for (UNI i = 0; i < syntax.size(); ++i)
		{
			string key_grammer = syntax.at(i);

			set<string> checked_set;

			// 是终结符而且不是$
			if (ifEndSign(key_grammer[0])
				&& key_grammer[0] != '$')
			{
				string temp = polyfillChar(key_grammer[0]);
				(*insert_set).insert(temp);
				// continue;
			}

			// 不是终结符，递归查找下一个
			else if ((!ifEndSign(key_grammer[0]) 
				&& key_grammer[0] != count_key))
			{
				
				// 非终结符但是能导出空串，且下一个符号为终结符
				if (checkEnd(polyfillChar(key_grammer[0]), &checked_set) 
					&& key_grammer.length() > 1
					&& ifEndSign(key_grammer[1]))
				{
					(*insert_set).insert(polyfillChar(key_grammer[1]));
				}
				calculateFirst(insert_set, key_grammer[0], word_vector);
			}
		}
	}

	// 查找是否本句文法能推导出$
	// Param: key {string} - 查找的键值
	//		  checked_set {set<string>*} - 已确认set，防止无限循环
	// Return: true - 能推出$
	//			false - 不能推出$
	bool FirstWord::checkEnd(string key, set<string>* checked_set) const
	{
		bool flag = false;
		checkEnd(key, checked_set, &flag);

		if (flag)
		{
			return true;
		}
		return false;
	}

	void FirstWord::checkEnd(string key, set<string>* checked_set, bool* flag) const
	{
		auto it = first.find(key);
		string next_key;


		if (it != first.end())
		{
			auto k = it->second.begin(); // set

										 // 非终结符
			if (!ifEndSign((*k)[0]) && (*k) != key)
			{
				next_key = (*k)[0];
			}

			// 读集合
			for (auto i = k; i != it->second.end(); ++i)
			{
				// 读字串
				for (unsigned int j = 0; j < (*i).length(); ++j)
				{
					if ((*i)[j] == '$')
					{
						*flag = true;
						// return true;
						return;
					}
				}
			}
		}

		// 递归查找
		if ((*checked_set).find(next_key) == (*checked_set).end())
		{
			(*checked_set).insert(key);
			checkEnd(next_key, checked_set, flag);
		}

		/*if (*flag == true)
		{
			return true;
		}

		return false;*/
	}


	void FirstWord::insertSet(string key, set<string>*insert_set)
	{
		auto if_key = first.find(key);
		if (if_key != first.end())
		{
			set<string>concat_set = if_key->second;
			for (auto concat_count = concat_set.begin();
				concat_count != concat_set.end();
				++concat_count)
			{
				(*insert_set).insert((*concat_count));
			}
			first.erase(if_key);
		}
		first.insert(map<string, set<string>>::value_type(key, (*insert_set)));
	}


	map<string, set<string>> FirstWord::getFirst() const
	{
		return first;
	}

	string FirstWord::polyfillChar(char new_char)
	{
		char a[2];
		a[0] = new_char;
		a[1] = '\0';

		return a;
	}
}